/*
	author: TangQiao , Wind @ Beijing Normal University

	problem name: Highways
	
	source :  PKU Online Judge
	
	problem type: 图论 最小生成树

	
	problem solution: prim 算法
	
		
	faults:本来是输出最小树的最大值,我误认为是求最大树的最小值.
	
	date : 2005.7.13 北大个人练习赛
	
*/
#include <stdio.h>
#include <string.h>
#include <math.h>

int dis[505][505];
int n;

struct dddef
{
	int start,end;
	int v;
}dd[505];

main()
{
//	freopen("input","r",stdin);
	int icase;
	int i,j,k;
	int min;

	scanf("%d", &icase);
	while (icase-->0)
	{
		scanf("%d", &n);
		memset(dd,0,sizeof(dd));
		for (i=1;i<=n;i++)
			for (j=1;j<=n;j++)
				scanf("%d", &dis[i][j]);
		for (i=1;i<n;i++)
		{
			dd[i].v=dis[1][i+1];
			dd[i].start=1;
			dd[i].end=i+1;
		}
		
		int minsite;
		int nod;
		for (i=1;i<n;i++)
		{
			minsite=i;
			for (j=i;j<n;j++)
				if (dd[minsite].v>dd[j].v)
					minsite=j;
			dd[0]=dd[i];
			dd[i]=dd[minsite];
			dd[minsite]=dd[0];
			nod=dd[i].end;
			for (k=i+1;k<n;k++)
				if (dd[k].v>dis[nod][dd[k].end])
				{
					dd[k].v=dis[nod][dd[k].end];
					dd[k].start=nod;
				}
		}
		/*
		for (i=1;i<n;i++) 
		{
			printf("start %d, end %d,length %d\n", dd[i].start,dd[i].end,dd[i].v);
		}*/
		min=dd[1].v;
		for (i=1;i<n;i++)
			if (min<dd[i].v)
				min=dd[i].v;
		printf("%d\n", min);

	}

	return 0;
}